package com.jia.leetCode;

/**
 * @program: Leetcode
 * @description: https://leetcode-cn.com/problems/counting-bits/submissions/
 * @author: STU756
 * @create: 2020-08-21 14:08
 */
public class Pro0338 {
    public int[] countBits(int num) {
        //f[n] = f[n >> 1] + (n & 1)  f(n)表示0到n为1总个数
        int[] f = new int[num+1];
        f[0] = 0;
        for(int i = 1; i <= num; i++) {
            f[i] = f[i>>1] + (i & 0x1);
        }
        return f;
    }
}
